package com.tgy.排序;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/***
 * @ClassName: Bucket
 * @Description: 桶排序
 * @Auther: tanggy3
 * @Date: 9:51 2022/8/31
 * @version : V1.0
 */
public class BucketSort {
    public static void main(String[] args) {
        int arr[] = {1, 8, -7, 44, 42, 46, 38, 34, 33, 17, 15, 16, 27, 28, 24};
        System.out.println(Arrays.toString(CountingSort.getArrCountF(arr)));
        System.out.println(Arrays.toString(bucketSort(arr, 10)));
    }

    /**
     * 很基础的排序，需要借助其他排序算法，不然就自己递归
     * 速度和分配桶的方式有很大的关系
     * @param arr
     * @param bucketSize 分配几个桶的依据
     * @return
     */
    static int[] bucketSort(int arr[], int bucketSize) {
        int[] arrCountF = CountingSort.getArrCountF(arr);
        //得到桶的数量，这里要记得加一。因为是取余
        int bucketCount = arrCountF[0] / bucketSize + 1;
        //每个桶都为一个链表
        List[] bucket = new ArrayList[bucketCount];
        for (int i = 0; i < bucket.length; i++) {
            //初始化每一个桶，设置为一个链表，好扩容也好桶内排序
            bucket[i] = new ArrayList<Integer>();
        }
        int index = 0;
        //遍历原始数组，把数字按照规则放入对应编号的桶中
        for (int i : arr) {
            index = i / bucketSize;
            bucket[index].add(i);
        }
        //每个桶自己排序
        int arrIndex = 0;
        for (int i = 0; i < bucketCount; i++) {
            List list = bucket[i];
            list.sort(null);
            for (int l = 0; l < list.size(); l++) {
                arr[arrIndex++] = (int) list.get(l);
            }
        }
        return arr;
    }
}
